解題程式碼

var reverseBetween = function (head, left, right) {
  const dummy = new ListNode(0, head);
  let prev = dummy;

  for (let i = 0; i < left - 1; i++) {
    prev = prev.next;
  }

  let cur = prev.next;

  for (let i = left; i < right; i++) {
    const temp = cur.next;
    cur.next = temp.next;
    temp.next = prev.next;
    prev.next = temp;
  }
  return dummy.next;
};

解題思路、演算法

屬於 206 題的變化，先用迴圈找到要反轉的前一個節點 prev，和要開始翻轉的節點 cur，然後在 left 和 right 的範圍內調整各節點 pointer。

https://imgur.com/a/H8lMC8l

解法的時間、空間複雜度

時間複雜度: O(n)
空間複雜度: O(1)

參考資料

反转链表 II

方法 2

【视频】又写错了？一个视频讲透！（Python/Java/C++/Go）

和上面解題程式碼不一樣的思路

var reverseBetween = function (head, left, right) {
  const dummy = new ListNode(0, head);
  let p0 = dummy;
  for (let i = 0; i < left - 1; i++) {
    p0 = p0.next;
  }

  let pre = null;
  let cur = p0.next;
  for (let i = left; i < right + 1; i++) {
    const nxt = cur.next;
    cur.next = pre; // 每次循环只修改一个 next，方便大家理解
    pre = cur;
    cur = nxt;
  }

  p0.next.next = cur;
  p0.next = pre;
  return dummy.next;
};

贾考博 LeetCode 92. Reverse Linked List II

LeetCode 92 - Reverse Linked List II